#pragma once
//把a[s..m] 调整为大项堆
//假设除a[s]之外，其他元素都符合大顶堆的定义
template <typename E>
void HeapAdjust(E a[], int s, int m)
{
    E tmp = a[s];
    for (int j = 2 * s + 1; j <= m; j = 2 * s + 1)
    {
        if (j < m && a[j + 1] > a[j])
            j++;
        if (a[j] <= tmp)
            break;
        a[s] = a[j];
        s = j;
    }
    a[s] = tmp;
}
//堆排序
template <typename E>
void HeapSort(E a[], int n)
{
    //建立大顶堆
    for (int i = (n - 3) / 2; i >= 0; i--)
        HeapAdjust(a, i, n - 1);
    // 继续堆排序
    for (int i = n - 1; i > 0; i--)
    {
    std::swap(a[0], a[i]);
        HeapAdjust(a, 0,i - 1);
    }
}